/*
https://leetcode.cn/problems/online-majority-element-in-subarray/solution/san-chong-fang-fa-bao-li-fen-kuai-xian-duan-shu-by/
 */
import java.util.ArrayList;
import java.util.List;

public class Solution1157 {

    public static class Node{
        int val;
        int count;
        int L;
        int R;
        Node left;
        Node right;

        public Node(int l,int r,int[] arr){
            L=l;
            R=r;
            if (l==r){
                val=arr[l];
                count=1;
            }else{
                int mid=(l+r)/2;
                left=new Node(l,mid,arr);
                right=new Node(mid+1,r,arr);
                if (left.val==right.val){
                    val=left.val;
                    count=left.count+ right.count;
                }else{
                    if (left.count> right.count){
                        val= left.val;
                        count= left.count- right.count;
                    }else{
                        val= right.val;
                        count= right.count- left.count;
                    }
                }
            }
        }

        public Node(int val, int count) {
            this.val = val;
            this.count = count;
        }

        public Node search(int l, int r){
            if (l>R || r<L){
                return null;
            }
            if (l<=L && r>=R){
                return new Node(val,count);
            }
            Node LL=left.search(l,r);
            Node RR=right.search(l,r);
            if (LL==null){
                return RR;
            }else if (RR==null){
                return LL;
            }else {
                if (LL.val==RR.val){
                    return new Node(LL.val,LL.count+ RR.count);
                }else{
                    if (LL.count> RR.count){
                        return new Node(LL.val, LL.count- RR.count);
                    }else{
                        return new Node(RR.val, RR.count- LL.count);
                    }
                }
            }
        }
    }

    Node node;
    List<Integer>[] lists=new ArrayList[20005];

    public Solution1157(int[] arr) {
        node=new Node(0,arr.length-1,arr);
        for (int i=1;i<=20000;i++){
            lists[i]=new ArrayList<>();
        }
        for (int i=0;i<arr.length;i++){
            lists[arr[i]].add(i);
        }
    }

    public int query(int left, int right, int threshold) {
        Node n=node.search(left,right);
        if (n==null){
            return -1;
        }
        int p=n.val;
        List<Integer> target=lists[p];
        int l=0,r=target.size()-1,L=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (target.get(mid)>=left){
                L=mid;
                r=mid-1;
            }else {
                l=mid+1;
            }
        }
        l=0;
        r=target.size()-1;
        int R=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (target.get(mid)<=right){
                R=mid;
                l=mid+1;
            }else {
                r=mid-1;
            }
        }
        if (R-L+1>=threshold){
            return p;
        }else {
            return -1;
        }
    }

    public static void main(String[] args) {
        Solution1157 solution1157=new Solution1157(new int[]{1,1,2,2,1,1});
        System.out.println(solution1157.query(0,5,4));
        System.out.println(solution1157.query(0,3,3));
        System.out.println(solution1157.query(2,3,2));
    }
}
